package Tree;

/**
 * 用来判断给定的树是否是已知树的子树
 * @author Administrator
 */
public class JudgeSubTree {
	public static void main(String[] args) {
		int a[] = { 10, 6, 21, 5, 8, 8, 22, 12 };
		BinaryTreeCreate tree = new BinaryTreeCreate();
		for (int i = 0; i < a.length; i++) {
			// 根节点设为null
			tree.createBinaryTree(tree.root, a[i]);
		}
		System.out.println("----");
		// 给定的树的结构
		int b[] = { 6, 5, 8, 8, 5 };
		BinaryTreeCreate subtree = new BinaryTreeCreate();
		for (int i = 0; i < b.length; i++) {
			// 根节点设为null
			subtree.createBinaryTree(subtree.root, b[i]);
		}
		JudgeSubTree test = new JudgeSubTree();
		System.out.print(test.isSubTree(tree.root, subtree.root));
	}

	public boolean isSubTree(TreeNode node1, TreeNode node2) {
		boolean result = false;
		if (node1 != null && node2 != null) {
			if (node1.val == node2.val) {
				result = containAll(node1, node2);
			}
			// 如果第一次没有找到，继续找.从左子树开始
			if (!result) {
				result = isSubTree(node1.left, node2);
			}
			// 找右子树
			if (!result) {
				result = isSubTree(node1.right, node2);
			}
		}
		return result;
	}

	// 判断子树与父树的结点值是否全部相等
	public boolean containAll(TreeNode node1, TreeNode node2) {
		// 注意，这个if要放在前面，因为一旦子树的左右结点之一为null，那么不管父树是否有结点都返回true。
		// 子树的结点空，返回true。因为说明父树包含了子树
		if (node2 == null) {
			return true;
		}
		// 如果父树的结点为空了，那么就返回false
		if (node1 == null) {
			return false;
		}
		/*
		 * //这里不能这样写，比如5-6-4(中序)，一旦两个值相等就返回true了，应该是不等于的话返回false。
		 * if(node1.value==node2.value){ return true; }
		 */
		if (node1.val != node2.val) {
			return false;
		}
		System.out.println("see is containAll");
		// 如果等于的话就执行递归
		return containAll(node1.left, node2.left)
				&& containAll(node1.right, node2.right);
	}
}
